<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8" />
   
  <meta name="keywords" content="Java Python" />
   
  <meta name="description" content="From Zero to Hero" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    二分查找-合集总结 |  朱酱酱的学习博客
  </title>
  <meta name="generator" content="hexo-theme-yilia-plus">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/css/style.css">

  
<script src="/js/pace.min.js"></script>


  

  

<link rel="alternate" href="/atom.xml" title="朱酱酱的学习博客" type="application/atom+xml">
</head>

</html>

<body>
  <div id="app">
    <main class="content">
      <section class="outer">
  <article id="post-LeetcodeExplore/二分查找-合集" class="article article-type-post" itemscope
  itemprop="blogPost" data-scroll-reveal>

  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  二分查找-合集总结
</h1>
  

    </header>
    

    
    <div class="article-meta">
      <a href="/2020/07/02/LeetcodeExplore/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE-%E5%90%88%E9%9B%86/" class="article-date">
  <time datetime="2020-07-02T07:52:53.000Z" itemprop="datePublished">2020-07-02</time>
</a>
      
      
      
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">9.9k字</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">40分钟</span>
        </span>
    </span>
</div>

      
    </div>
    

    
    
    <div class="tocbot"></div>





    

    <div class="article-entry" itemprop="articleBody">
      


      

      
      <h1 id="二分查找-合集总结"><a href="#二分查找-合集总结" class="headerlink" title="二分查找-合集总结"></a>二分查找-合集总结</h1><p>（本系列是针对Leetcode上常见的二分查找题目进行总结。）</p>
<p><strong>总体思想：把待搜索的目标值留在最后判断，在循环体内不断地把不符合题目要求的子区间排除掉，在退出循环以后，因为只剩下 1 个数没有看到，它要么是目标元素，要么不是目标元素，单独判断即可。</strong></p>
<p>用这种思路写二分<strong>不容易出错，需要考虑的细节最少</strong>。</p>
<ul>
<li>这种思路也非常符合“二分”这个名字，就是把【待搜索的区间】分为【有目标元素的区间】和【不包含目标元素的区间】，排除掉【不包含目标元素的区间】，剩下的就是有【目标元素的区间】。</li>
</ul>
<ul>
<li>初学写二分查找的问题是：跳步厉害，写下 left = mid 或者 right = mid - 1 等代码的时候，一定要搞清楚是什么意思，必要的时候写上注释，帮助自己思考和以后复查代码。</li>
</ul>
<ul>
<li>算法问题建议更多地理解思想，思考为什么这样写，而不建议背代码，背模板。即使要用代码和模板，例如并查集、线段树这种，也应该先把它们保存到自己的 github 代码仓库里，要用的时候去复制粘贴。</li>
</ul>
<p><strong>PS：分类是liweiwei老哥总结好的，在他的分类下，下文将以自己的思想将题目串通总结起来。</strong></p>
<p><strong>二分总结链接</strong>：<a href="https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/" target="_blank" rel="noopener">https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/</a></p>
<h1 id="1-题目分类"><a href="#1-题目分类" class="headerlink" title="1. 题目分类"></a>1. 题目分类</h1><p><strong>「力扣」上的二分查找问题主要有这三类题型。</strong></p>
<p><strong>一、在数组中查找符合条件的元素的索引</strong></p>
<p>一般而言这个数组是有序的，也可能是半有序的，但不大可能是无序的。</p>
<table>
<thead>
<tr>
<th><strong>题目</strong></th>
<th>提示与题解</th>
</tr>
</thead>
<tbody><tr>
<td><a href="https://leetcode-cn.com/problems/binary-search/" target="_blank" rel="noopener">704. 二分查找</a></td>
<td>二分查找的模板问题，使用本题解介绍的方法就要注意，需要“后处理”。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/" target="_blank" rel="noopener">34. 在排序数组中查找元素的第一个和最后一个位置</a></td>
<td>查找边界问题，<a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/si-lu-hen-jian-dan-xi-jie-fei-mo-gui-de-er-fen-cha/" target="_blank" rel="noopener">题解（有视频讲解）</a>。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/" target="_blank" rel="noopener">33. 搜索旋转排序数组</a></td>
<td><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/er-fen-fa-python-dai-ma-java-dai-ma-by-liweiwei141/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/" target="_blank" rel="noopener">81. 搜索旋转排序数组 II</a></td>
<td><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/er-fen-cha-zhao-by-liweiwei1419/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/" target="_blank" rel="noopener">153. 寻找旋转排序数组中的最小值</a></td>
<td><a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-fa-fen-zhi-fa-python-dai-ma-java-dai-ma-by-/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/" target="_blank" rel="noopener">154. 寻找旋转排序数组中的最小值 II</a></td>
<td><a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/er-fen-fa-fen-zhi-fa-python-dai-ma-by-liweiwei1419/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/" target="_blank" rel="noopener">300. 最长上升子序列</a></td>
<td>二分查找的思路需要理解，代码很像第 35 题，<a href="https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/" target="_blank" rel="noopener">题解</a>。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/h-index-ii/" target="_blank" rel="noopener">275. H指数 II</a></td>
<td><a href="https://leetcode-cn.com/problems/h-index-ii/solution/jian-er-zhi-zhi-er-fen-cha-zhao-by-liweiwei1419-2/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-in-mountain-array/" target="_blank" rel="noopener">1095. 山脉数组中查找目标值</a></td>
<td><a href="https://leetcode-cn.com/problems/find-in-mountain-array/solution/shi-yong-chao-hao-yong-de-er-fen-fa-mo-ban-python-/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/" target="_blank" rel="noopener">852. 山脉数组的峰顶索引（简单）</a></td>
<td></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-k-closest-elements/" target="_blank" rel="noopener">658. 找到 K 个最接近的元素（中等）</a></td>
<td><a href="https://leetcode-cn.com/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/" target="_blank" rel="noopener">题解</a>，这个问题二分的写法需要做复杂的分类讨论，可以放在以后做。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/" target="_blank" rel="noopener">4. 寻找两个有序数组的中位数</a></td>
<td><a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/" target="_blank" rel="noopener">官方题解（有视频讲解）</a>，<a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/" target="_blank" rel="noopener">题解</a></td>
</tr>
</tbody></table>
<p><strong>二、在一个有上下界的区间里搜索一个整数</strong></p>
<table>
<thead>
<tr>
<th><strong>题目</strong></th>
<th><strong>提示与题解</strong></th>
</tr>
</thead>
<tbody><tr>
<td><a href="https://leetcode-cn.com/problems/sqrtx/" target="_blank" rel="noopener">69. 平方根</a></td>
<td>在一个整数范围里查找一个整数，也是二分查找法的应用场景，<a href="https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/" target="_blank" rel="noopener">题解</a>。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-the-duplicate-number/" target="_blank" rel="noopener">287. 寻找重复数</a></td>
<td><a href="https://leetcode-cn.com/problems/find-the-duplicate-number/solution/er-fen-fa-si-lu-ji-dai-ma-python-by-liweiwei1419/" target="_blank" rel="noopener">题解</a>。在一个整数范围里查找一个整数。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/guess-number-higher-or-lower/" target="_blank" rel="noopener">374. 猜数字大小</a></td>
<td><a href="https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/" target="_blank" rel="noopener">1300. 转变数组后最接近目标值的数组和</a></td>
<td><a href="https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/er-fen-cha-zhao-by-liweiwei1419-2/" target="_blank" rel="noopener">题解</a></td>
</tr>
</tbody></table>
<p><strong>三. 判别条件是一个函数</strong></p>
<table>
<thead>
<tr>
<th><strong>题目</strong></th>
<th><strong>提示与题解</strong></th>
</tr>
</thead>
<tbody><tr>
<td><a href="https://leetcode-cn.com/problems/first-bad-version/" target="_blank" rel="noopener">278. 第一个错误的版本</a></td>
<td></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/split-array-largest-sum/" target="_blank" rel="noopener">410. 分割数组的最大值</a></td>
<td>经典问题，判别函数的写法很有技巧，<a href="https://leetcode-cn.com/problems/split-array-largest-sum/solution/er-fen-cha-zhao-by-liweiwei1419-4/" target="_blank" rel="noopener">题解</a>。</td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/find-k-closest-elements/" target="_blank" rel="noopener">658. 找到 K 个最接近的元素</a></td>
<td><a href="https://leetcode-cn.com/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/koko-eating-bananas/" target="_blank" rel="noopener">875. 爱吃香蕉的珂珂</a></td>
<td><a href="https://leetcode-cn.com/problems/koko-eating-bananas/solution/er-fen-cha-zhao-ding-wei-su-du-by-liweiwei1419/" target="_blank" rel="noopener">题解</a></td>
</tr>
<tr>
<td><a href="https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/" target="_blank" rel="noopener">1300. 转变数组后最接近目标值的数组和</a></td>
<td><a href="https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/er-fen-cha-zhao-by-liweiwei1419-2/" target="_blank" rel="noopener">题解</a></td>
</tr>
</tbody></table>
<a id="more"></a>



<h1 id="2-分类1：在数组中查找符合条件的元素的索引"><a href="#2-分类1：在数组中查找符合条件的元素的索引" class="headerlink" title="2. 分类1：在数组中查找符合条件的元素的索引"></a>2. 分类1：在数组中查找符合条件的元素的索引</h1><h2 id="题目1：704-二分查找"><a href="#题目1：704-二分查找" class="headerlink" title="题目1：704. 二分查找"></a>题目1：<a href="https://leetcode-cn.com/problems/binary-search/" target="_blank" rel="noopener">704. 二分查找</a></h2><p><strong>1. 题目描述：</strong></p>
<p>给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">示例 1:</span><br><span class="line"></span><br><span class="line">输入: nums &#x3D; [-1,0,3,5,9,12], target &#x3D; 9</span><br><span class="line">输出: 4</span><br><span class="line">解释: 9 出现在 nums 中并且下标为 4</span><br><span class="line"></span><br><span class="line">示例 2:</span><br><span class="line"></span><br><span class="line">输入: nums &#x3D; [-1,0,3,5,9,12], target &#x3D; 2</span><br><span class="line">输出: -1</span><br><span class="line">解释: 2 不存在 nums 中因此返回 -1</span><br></pre></td></tr></table></figure>



<p><strong>提示：</strong></p>
<ol>
<li>你可以假设 <code>nums</code> 中的所有元素是不重复的。</li>
<li><code>n</code> 将在 <code>[1, 10000]</code>之间。</li>
<li><code>nums</code> 的每个元素都将在 <code>[-9999, 9999]</code>之间。</li>
</ol>
<p><strong>2.算法思路</strong></p>
<ul>
<li>经典的二分查找法（暂时不在这里详细叙述，各位有算法基础的大佬应该闭着眼睛都能写）</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt;= right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] == target)&#123;</span><br><span class="line">                <span class="keyword">return</span> mid;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target)&#123;</span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                right = mid - <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度：O(log<em>N</em>) &lt; O(N) </li>
<li>空间复杂度：O(1)</li>
</ul>
<p>上述的做法实际上是将<strong>待搜索的区间分为了三个区间</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200705/164445962.png" alt="mark"></p>
<p><strong>这种写法的弊端是：返回的边界问题（读者可以想一想弊端具体发生的情况）</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200705/164615121.png" alt="mark"></p>
<p><strong>接下来提供另外一种：二分查找的思想（排除法）</strong></p>
<ul>
<li><strong>mid被分到左边区间</strong></li>
<li><strong>mid被分到右边区间</strong></li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200705/164822418.png" alt="mark"></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200705/165100657.png" alt="mark"></p>
<p><strong>死循环可能产生的原因：</strong></p>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200705/165635068.png" alt="mark"></p>
<h2 id="题目2：35-搜索插入位置"><a href="#题目2：35-搜索插入位置" class="headerlink" title="题目2：35. 搜索插入位置"></a>题目2：<a href="https://leetcode-cn.com/problems/search-insert-position/" target="_blank" rel="noopener">35. 搜索插入位置</a></h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">searchInsert</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (len == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (nums[len - <span class="number">1</span>] &lt; target)&#123;</span><br><span class="line">            <span class="keyword">return</span> len;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="comment">// 什么时候不是解</span></span><br><span class="line">            <span class="comment">// 如果严格小于不是解</span></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &lt; target)&#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索的区间是[mid + 1,right]</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 相反的区间[left,mid]</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析：</strong></p>
<ul>
<li>时间复杂度：O(logN)，这里 N 是数组的长度，每一次都将问题的规模缩减为原来的一半，因此时间复杂度是对数级别的；</li>
<li>空间复杂度：O(1)。</li>
</ul>
<h2 id="题目3：34-在排序数组中查找元素的第一个和最后一个位置"><a href="#题目3：34-在排序数组中查找元素的第一个和最后一个位置" class="headerlink" title="题目3：34. 在排序数组中查找元素的第一个和最后一个位置"></a>题目3：<a href="https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/" target="_blank" rel="noopener">34. 在排序数组中查找元素的第一个和最后一个位置</a></h2><p>题目描述：</p>
<p>给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。</p>
<p>你的算法时间复杂度必须是 O(log n) 级别。</p>
<p>如果数组中不存在目标值，返回 [-1, -1]。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">示例 <span class="number">1</span>:</span><br><span class="line"></span><br><span class="line">输入: nums = [<span class="number">5</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">8</span>,<span class="number">10</span>], target = <span class="number">8</span></span><br><span class="line">输出: [<span class="number">3</span>,<span class="number">4</span>]</span><br><span class="line"></span><br><span class="line">示例 <span class="number">2</span>:</span><br><span class="line"></span><br><span class="line">输入: nums = [<span class="number">5</span>,<span class="number">7</span>,<span class="number">7</span>,<span class="number">8</span>,<span class="number">8</span>,<span class="number">10</span>], target = <span class="number">6</span></span><br><span class="line">输出: [-<span class="number">1</span>,-<span class="number">1</span>]</span><br></pre></td></tr></table></figure>



<p><strong>算法思想</strong></p>
<ul>
<li><code>nums[mid] &lt; target</code> 一定不是开始位置的解</li>
<li><code>nums[mid] &gt; target</code> 一定不是结束位置的解 </li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">int</span>[] searchRange(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (len == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>,-<span class="number">1</span>&#125;;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 开始位置</span></span><br><span class="line">        <span class="keyword">int</span> firstPosition = findFirstPosition(nums,target);</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 如果开始位置都没找到这个元素</span></span><br><span class="line">        <span class="keyword">if</span> (firstPosition == -<span class="number">1</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>,-<span class="number">1</span>&#125;;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 结束位置</span></span><br><span class="line">        <span class="keyword">int</span> lastPosition = findLastPosition(nums,target);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;firstPosition,lastPosition&#125;;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findFirstPosition</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="comment">// 下取整</span></span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 什么时候不是解</span></span><br><span class="line">            <span class="comment">// 严格小于不是解</span></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &lt; target)&#123;</span><br><span class="line">                <span class="comment">// 下一轮 搜索区间[mid + 1,right]</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// nums[mid] &gt;= target</span></span><br><span class="line">                <span class="comment">// 搜索区间是[left,mid]</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 对查找的数进行判断</span></span><br><span class="line">        <span class="keyword">if</span> (nums[left] == target)&#123;</span><br><span class="line">            <span class="keyword">return</span> left;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 这时候如果向下取整会有死循环的产生</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findLastPosition</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="comment">// 上取整</span></span><br><span class="line">            <span class="keyword">int</span> mid = (left + right + <span class="number">1</span>) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 大于一定不是解</span></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &gt; target)&#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索的区间是[left,mid - 1]</span></span><br><span class="line">                right = mid - <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索的区间是[mid,right]</span></span><br><span class="line">                left = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>复杂度分析：</p>
<ul>
<li><strong>时间复杂度</strong>：O(log N)，这里 N 是数组的长度，两个子问题都是二分查找，因此时间复杂度为对数级别。</li>
<li><strong>空间复杂度</strong>：O(1)，只使用了常数个数的辅助变量、指针。</li>
</ul>
<h2 id="题目4：33-搜索旋转排序数组"><a href="#题目4：33-搜索旋转排序数组" class="headerlink" title="题目4：33. 搜索旋转排序数组"></a>题目4：<a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/" target="_blank" rel="noopener">33. 搜索旋转排序数组</a></h2><p><strong>题目描述</strong></p>
<p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。</p>
<p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。</p>
<p>搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。</p>
<p>你可以假设数组中不存在重复的元素。</p>
<p>你的算法时间复杂度必须是 O(log n) 级别。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">示例 <span class="number">1</span>:</span><br><span class="line"></span><br><span class="line">输入: nums = [<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>], target = <span class="number">0</span></span><br><span class="line">输出: <span class="number">4</span></span><br><span class="line">    </span><br><span class="line">    </span><br><span class="line">示例 <span class="number">2</span>:</span><br><span class="line"></span><br><span class="line">输入: nums = [<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>,<span class="number">7</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">2</span>], target = <span class="number">3</span></span><br><span class="line">输出: -<span class="number">1</span></span><br></pre></td></tr></table></figure>



<p><strong>算法思路</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 二分法</span></span><br><span class="line"><span class="comment">// 讨论中间元素和有边界的关系</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">search</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (len == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right + <span class="number">1</span>) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &lt; nums[right])&#123;</span><br><span class="line">                <span class="comment">// 使用上取整的中间数，必须在上面的 mid 表达式的括号里 + 1</span></span><br><span class="line">                <span class="keyword">if</span> (nums[mid] &lt;= target &amp;&amp; target &lt;= nums[right])&#123;</span><br><span class="line">                    <span class="comment">// 下一轮搜索区间是[mid,right]</span></span><br><span class="line">                    left = mid;</span><br><span class="line">                &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="comment">// 只要上面对了，这个区间是上面区间的反面区间，下一轮搜索区间是 [left, mid - 1]</span></span><br><span class="line">                    right = mid - <span class="number">1</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123; <span class="comment">// nums[mid] &gt;= nums[right]</span></span><br><span class="line">                <span class="comment">// [left, mid] 有序，但是为了和上一个 if 有同样的收缩行为，</span></span><br><span class="line">                <span class="comment">// 故意强行认为[left, mid - 1]有序</span></span><br><span class="line">                <span class="comment">// 当区间只剩下2个元素的时候 int mid = (left + right + 1) &gt;&gt;&gt; 1 ;一定会取到右边</span></span><br><span class="line">                <span class="comment">// 此时mid - 1不会越界</span></span><br><span class="line">                <span class="keyword">if</span> (nums[left] &lt;= target &amp;&amp; target &lt;= nums[mid - <span class="number">1</span>])&#123;</span><br><span class="line">                    right = mid - <span class="number">1</span>;</span><br><span class="line">                &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="comment">// 下一轮搜索区间是[mid,right]</span></span><br><span class="line">                    left = mid;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 有可能不存在目标元素，因此还需要做一次判断</span></span><br><span class="line">        <span class="keyword">if</span> (nums[left] == target)&#123;</span><br><span class="line">            <span class="keyword">return</span> left;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>  -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>





<h2 id="题目-5-：-153-寻找旋转排序数组中的最小值"><a href="#题目-5-：-153-寻找旋转排序数组中的最小值" class="headerlink" title="题目 5 ： 153. 寻找旋转排序数组中的最小值"></a>题目 5 ： <a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/" target="_blank" rel="noopener">153. 寻找旋转排序数组中的最小值</a></h2><p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。</p>
<p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。</p>
<p>请找出其中最小的元素。</p>
<p>你可以假设数组中不存在重复元素。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: [3,4,5,1,2]</span><br><span class="line">输出: 1</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: [4,5,6,7,0,1,2]</span><br><span class="line">输出: 0</span><br></pre></td></tr></table></figure>



<p><strong>思路</strong></p>
<ul>
<li>旋转排序数组，几乎都是有序的数组，也可以通过比较特定位置的元素判断达到”减治“的效果（逐渐缩小区间）</li>
<li>很自然地，我们会看<strong>中间数（</strong>位于待搜索区间中间位置的元素，由于不是有序数组，因此不能称之为<strong>中位数</strong>）。</li>
</ul>
<p>这时候有两个思路：</p>
<ul>
<li>思路一：看看搜索区间<strong>左边界</strong>和 ”<strong>中间数</strong>“（注意这里不是中位数），是不是可以缩小搜索区间的范围；</li>
<li>思路 2：看看当前搜索区间的<strong>右边界</strong>和“<strong>中间数</strong>”（注意这里不是中位数），是不是可以缩小搜索区间的范围；</li>
</ul>
<p>要想清楚这个问题，我们不妨举几个例子。</p>
<p><strong>针对思路1：</strong></p>
<p>例 1：<code>[1, 2, 3, 4, 5]</code></p>
<p>例 2：<code>[2, 3, 4, 5, 1]</code></p>
<ul>
<li>这两个例子中 ”中间数“都比左边界大，但是旋转排序数组的最小值一个在中间数的左边，一个在中间数的右边，因此思路1是不可行的。</li>
</ul>
<p><strong>针对思路2</strong></p>
<p>例 3：<code>[7, 8, 9, 10, 11, 12, 1, 2, 3]</code></p>
<p>例 4：<code>[7, 8, 1, 2, 3]</code></p>
<ul>
<li>中间数 11 比 3 大，因此中间数左边的数字都不可能是旋转排序数组的最小值，因此下一轮搜索的区间是 [mid + 1,right]</li>
<li>再看例4 ， 中间数到右边界是递增的， 1 比 3 小，那么中间数右边的数一定不是旋转排序数组的最小值，因此可以把中间数右边的数字排除，但是中间数有可能是整个数组的最小值，就如本例子，因此下一轮搜索区间是[left,mid] ,于是右边界 <code>right = mid</code></li>
</ul>
<p>从例 3 和例 4 可以看出，<strong>不论中间数比右边界大，还是中间数比右边界小，我们都可以排除掉将近一半的元素，把原始问题转换成一个规模更小的子问题，这正是“减而治之”思想的体现</strong>，<strong>因此思路 2 可行。</strong></p>
<p><strong>代码实现：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMin</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"数组为空，无最小元素"</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &gt; nums[right])&#123;</span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// nums[mid] &lt; nums[right](不存在重复的数字)</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 一定存在最小元素，因此无需再做判断</span></span><br><span class="line">        <span class="keyword">return</span> nums[left];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析：</strong></p>
<ul>
<li>时间复杂度：O(logn)</li>
<li>空间复杂度：O（1）</li>
</ul>
<h2 id="题目6-：-154-寻找旋转排序数组中的最小值-II"><a href="#题目6-：-154-寻找旋转排序数组中的最小值-II" class="headerlink" title="题目6 ： 154. 寻找旋转排序数组中的最小值 II"></a>题目6 ： <a href="https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/" target="_blank" rel="noopener">154. 寻找旋转排序数组中的最小值 II</a></h2><p><strong>题目描述</strong></p>
<p>假设按照升序排序的数组在预先未知的某个点上进行了旋转。</p>
<p>( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。</p>
<p>请找出其中最小的元素。</p>
<p>注意数组中可能存在重复的元素。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">示例 1：</span><br><span class="line"></span><br><span class="line">输入: [1,3,5]</span><br><span class="line">输出: 1</span><br><span class="line">示例 2：</span><br><span class="line"></span><br><span class="line">输入: [2,2,2,0,1]</span><br><span class="line">输出: 0</span><br></pre></td></tr></table></figure>



<p><strong>代码实现：</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 跟153题相比</span></span><br><span class="line"><span class="comment">// 数组中可能存在重复的元素。</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findMin</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (nums.length == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">"数组为空，无最小元素"</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (nums[mid] &gt; nums[right])&#123;</span><br><span class="line">                <span class="comment">// 说明左侧是升序序列</span></span><br><span class="line">                <span class="comment">// 下一轮搜索区间[mid,right]</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; nums[right])&#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索区间[left,mid]</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// nums[mid] == nums[right]</span></span><br><span class="line">                <span class="comment">// 例 5：[0, 1, 1, 1, 1, 1, 1]</span></span><br><span class="line">                <span class="comment">// 例 6：[1, 1, 1, 1, 0, 1, 1]</span></span><br><span class="line">                <span class="comment">// 目标值可能在中间数的左边，也有可能在中间数的右边</span></span><br><span class="line">                <span class="comment">// 此时看到了右边界，就把右边界排除掉就好了</span></span><br><span class="line">                <span class="comment">// 正是因为右边界和中间数相等，你去掉了右边界，中间数还在，就让中间数在后面的循环中再起效果</span></span><br><span class="line">                right--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> nums[left];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>





<p><strong>复杂度分析：</strong></p>
<ul>
<li>时间复杂度：O(logn) ,这里不太确定，因为right– 的操作。</li>
<li>空间复杂度：O（1）</li>
</ul>
<h2 id="题目7-：-H指数-II"><a href="#题目7-：-H指数-II" class="headerlink" title="题目7 ： H指数 II"></a>题目7 ： <a href="https://leetcode-cn.com/problems/h-index-ii/" target="_blank" rel="noopener">H指数 II</a></h2><p><strong>题目描述</strong></p>
<p>给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。</p>
<p>h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">示例:</span><br><span class="line"></span><br><span class="line">输入: citations = [<span class="number">0</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">5</span>,<span class="number">6</span>]</span><br><span class="line">输出: <span class="number">3</span> </span><br><span class="line">解释: 给定数组表示研究者总共有 <span class="number">5</span> 篇论文，每篇论文相应的被引用了 <span class="number">0</span>, <span class="number">1</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">6</span> 次。</span><br><span class="line">     由于研究者有 <span class="number">3</span> 篇论文每篇至少被引用了 <span class="number">3</span> 次，其余两篇论文每篇被引用不多于 <span class="number">3</span> 次，所以她的 h 指数是 <span class="number">3</span>。</span><br></pre></td></tr></table></figure>

<p>说明:</p>
<p>如果 h 有多有种可能的值 ，h 指数是其中最大的那个。</p>
<p>进阶：</p>
<p>这是 H指数 的延伸题目，本题中的 citations 数组是保证有序的。<br>你可以优化你的算法到<strong>对数时间复杂度吗？</strong></p>
<p><strong>方法：二分查找</strong></p>
<p>题目中说到：</p>
<blockquote>
<p>本题中的 citations 数组是保证有序的。</p>
</blockquote>
<p>并且还暗示</p>
<blockquote>
<p>你可以优化你的算法到对数时间复杂度吗？</p>
</blockquote>
<ul>
<li><p>因此，可以使用二分查找，二分查找这种非对即错的问题，个人觉得根据示例分析是一种不错的方法。</p>
<ul>
<li>就根据示例<code>citations = [0, 1, 3, 5, 6]</code>。</li>
<li>中位数是3，<code>citations[2]</code> 恰好也等于 3，这个 3 正好是边界，不太好分析 ，我把中位数改成了 2。</li>
<li>即： <code>citiations = [0,1,2,5,6]</code> 此时根据题目的意思，<strong>此时索引位2的那篇论文不能计入 h 指数（因为，如果算进去，则有3篇论文，但是这篇最小引用的文章才被引用两次）</strong></li>
</ul>
</li>
<li><p>因此，分析出 <code>h</code> 指数和以下两个指标有关：</p>
<ul>
<li><strong>某个索引 i 的  citiations 的取值</strong></li>
<li><strong>某个索引 i 到 citiations 末尾的长度，即区间<code>[i, len - 1]</code> 的长度，即 <code>len - 1 -i + 1 = len - i</code>。</strong></li>
</ul>
</li>
<li><p>如果<code>nums[i] &lt; len - i</code> 索引 <code>i</code> 必须后移一位，因此候选区间是<code>[i + 1,len - 1]</code> </p>
<ul>
<li>所以二分查找的下一轮区间是<code>left = i + 1</code> </li>
</ul>
</li>
<li><p>如果 <code>nums[i] &gt; len - i</code>的反面一定就是 <code>right = mid</code> ,看到 <code>left = i + 1</code>,可以知道分支排除了中位数，所以不会有死循环。</p>
</li>
<li><p>最后，返回的是区间的长度，区间长度是 <code>len - i</code></p>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 二分查找</span></span><br><span class="line"><span class="comment">// 思路：看nums[mid] 和 区间[mid,len - 1] 的长度</span></span><br><span class="line"><span class="comment">// 即 len - 1 - mid + 1 = len - mid</span></span><br><span class="line"><span class="comment">// [0, 1, 2, 5, 6] 为例子</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">hIndex</span><span class="params">(<span class="keyword">int</span>[] citations)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = citations.length;</span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (len == <span class="number">0</span> || citations[len - <span class="number">1</span>] == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = len - <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="comment">// 如果当前的h指数比长度小就去掉这个值</span></span><br><span class="line">            <span class="keyword">if</span> (citations[mid] &lt; len - mid)&#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索区间</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// citations[mid] &gt;= len - mid</span></span><br><span class="line">                <span class="comment">// 比长度大是满足的，应该让mid 往左走尝试看有没有更小的mid值</span></span><br><span class="line">                <span class="comment">// 可以满足mid 对应值大于等于从[mid,len - 1]的长度</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> len - left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度：O(logN) N是数组的长度</li>
<li>空间复杂度：O(1)</li>
</ul>
<h2 id="题目8-：-H-指数"><a href="#题目8-：-H-指数" class="headerlink" title="题目8 ：  H 指数"></a>题目8 ： <a href="https://leetcode-cn.com/problems/h-index/" target="_blank" rel="noopener"> H 指数</a></h2><p>给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。</p>
<p>h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）</p>
<p>例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。</p>
<p><strong>示例：</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入：citations &#x3D; [3,0,6,1,5]</span><br><span class="line">输出：3 </span><br><span class="line">解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。</span><br><span class="line">     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。</span><br></pre></td></tr></table></figure>



<p><strong>提示：本题和上述的区别是不是升序的数组</strong></p>
<p><strong>算法思路</strong></p>
<ol>
<li><strong>和上题一样，二分查找前加一个排序即可</strong></li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">hIndex</span><span class="params">(<span class="keyword">int</span>[] citations)</span> </span>&#123;</span><br><span class="line">        Arrays.sort(citations);</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> len = citations.length;</span><br><span class="line">        <span class="comment">// 特判</span></span><br><span class="line">        <span class="keyword">if</span> (len == <span class="number">0</span> || citations[len - <span class="number">1</span>] == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> right = citations.length - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 比后面的长度小就去掉这个值</span></span><br><span class="line">            <span class="comment">// 区间长度[mid,len - 1]</span></span><br><span class="line">            <span class="comment">// len - 1 - mid + 1</span></span><br><span class="line">            <span class="keyword">if</span> (citations[mid] &lt; len - mid)&#123;</span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 比后面的长度大，满足条件，下一轮搜索区间[left,right]</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 返回的是这个区间的长度(h指数)</span></span><br><span class="line">        <span class="keyword">return</span> len - left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析：</strong></p>
<ul>
<li><strong>时间复杂度</strong>：O(nlogn)</li>
<li><strong>空间复杂度</strong>： O（1）</li>
</ul>
<h2 id="题目9-：-山脉数组中查找目标值-（困难）"><a href="#题目9-：-山脉数组中查找目标值-（困难）" class="headerlink" title="题目9 ： 山脉数组中查找目标值 （困难）"></a>题目9 ： <a href="https://leetcode-cn.com/problems/find-in-mountain-array/" target="_blank" rel="noopener">山脉数组中查找目标值</a> （困难）</h2><p><strong>题目描述</strong></p>
<p>（这是一个 交互式问题 ）</p>
<p>给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。</p>
<p>如果不存在这样的下标 index，就请返回 -1。</p>
<p>你将 不能直接访问该山脉数组，<strong>必须通过 MountainArray 接口来获取数据</strong>：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）</span><br><span class="line">MountainArray.length() - 会返回该数组的长度</span><br></pre></td></tr></table></figure>



<p><strong>注意：</strong></p>
<p><strong>对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案</strong>。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。</p>
<p>为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：<a href="https://leetcode-cn.com/playground/RKhe3ave，请注意这" target="_blank" rel="noopener">https://leetcode-cn.com/playground/RKhe3ave，请注意这</a> 不是一个正确答案。</p>
<p><strong>方法：三次二分查找</strong></p>
<ul>
<li>理解什么是山脉数组，山脉数组可以分为两部分，一部分是<strong>前有序数组</strong>，一部分是<strong>后有序数组</strong></li>
<li>“前有序数组” 是升序数组，后有序数组是降序数组。</li>
<li>题目还告诉我们 “对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案” ，就在疯狂暗示你使用时间复杂度低的算法，对于有序数组当然使用 “二分查找法” 。</li>
</ul>
<p><strong>算法思路</strong></p>
<ul>
<li>求解这道题分为三部分<ul>
<li>第一步：先找到<code>mountaintop</code> 所在的索引</li>
<li>第二步：在前有序数组中找target所在的索引，如果找到了就返回，没有找到执行步骤3</li>
<li>第三步：如果步骤2 找不到，就在后有序降序数组中找<code>target</code> 所在的索引</li>
</ul>
</li>
</ul>
<ul>
<li>写出来的 3 个辅助方法的分支逻辑出奇地一样，在取中位数的时候，都取左中位数，才不会发生死循环。</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * // This is MountainArray's API interface.</span></span><br><span class="line"><span class="comment"> * // You should not implement it, or speculate about its implementation</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">interface</span> <span class="title">MountainArray</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span></span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">length</span><span class="params">()</span></span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MountainArrayImpl</span> <span class="keyword">implements</span> <span class="title">MountainArray</span> </span>&#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] arr;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MountainArrayImpl</span><span class="params">(<span class="keyword">int</span>[] arr)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.arr = arr;</span><br><span class="line">        <span class="keyword">this</span>.size = <span class="keyword">this</span>.arr.length;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">get</span><span class="params">(<span class="keyword">int</span> index)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.arr[index];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">length</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">this</span>.size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 特别注意：3 个辅助方法的分支出奇地一样，因此选中位数均选左中位数，才不会发生死循环</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findInMountainArray</span><span class="params">(<span class="keyword">int</span> target, MountainArray mountainArr)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> size = mountainArr.length();</span><br><span class="line">        <span class="comment">// 步骤 1：先找到山顶元素所在的索引</span></span><br><span class="line">        <span class="keyword">int</span> mountaintop = findMountaintop(mountainArr, <span class="number">0</span>, size - <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// 步骤 2：在前有序且升序数组中找 target 所在的索引</span></span><br><span class="line">        <span class="keyword">int</span> res = findFromSortedArr(mountainArr, <span class="number">0</span>, mountaintop, target);</span><br><span class="line">        <span class="keyword">if</span> (res != -<span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> res;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 步骤 3：如果步骤 2 找不到，就在后有序且降序数组中找 target 所在的索引</span></span><br><span class="line">        <span class="keyword">return</span> findFromInversedArr(mountainArr, mountaintop + <span class="number">1</span>, size - <span class="number">1</span>, target);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findMountaintop</span><span class="params">(MountainArray mountainArr, <span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 返回山顶元素</span></span><br><span class="line">        <span class="keyword">while</span> (l &lt; r) &#123;</span><br><span class="line">            <span class="keyword">int</span> mid = l + (r - l) / <span class="number">2</span>;</span><br><span class="line">            <span class="comment">// 取左中位数，因为进入循环，数组一定至少有 2 个元素</span></span><br><span class="line">            <span class="comment">// 因此，左中位数一定有右边元素，数组下标不会发生越界</span></span><br><span class="line">            <span class="keyword">if</span> (mountainArr.get(mid) &lt; mountainArr.get(mid + <span class="number">1</span>)) &#123;</span><br><span class="line">                <span class="comment">// 如果当前的数比右边的数小，它一定不是山顶</span></span><br><span class="line">                l = mid + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                r = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 根据题意，山顶元素一定存在，因此退出 while 循环的时候，不用再单独作判断</span></span><br><span class="line">        <span class="keyword">return</span> l;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findFromSortedArr</span><span class="params">(MountainArray mountainArr, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 在前有序且升序数组中找 target 所在的索引</span></span><br><span class="line">        <span class="keyword">while</span> (l &lt; r) &#123;</span><br><span class="line">            <span class="keyword">int</span> mid = l + (r - l) / <span class="number">2</span>;</span><br><span class="line">            <span class="keyword">if</span> (mountainArr.get(mid) &lt; target) &#123;</span><br><span class="line">                l = mid + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                r = mid;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 因为不确定区间收缩成 1个数以后，这个数是不是要找的数，因此单独做一次判断</span></span><br><span class="line">        <span class="keyword">if</span> (mountainArr.get(l) == target) &#123;</span><br><span class="line">            <span class="keyword">return</span> l;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">findFromInversedArr</span><span class="params">(MountainArray mountainArr, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 在后有序且降序数组中找 target 所在的索引</span></span><br><span class="line">        <span class="keyword">while</span> (l &lt; r) &#123;</span><br><span class="line">            <span class="keyword">int</span> mid = l + (r - l) / <span class="number">2</span>;</span><br><span class="line">            <span class="comment">// 与 findFromSortedArr 方法不同的地方仅仅在于由原来的小于号改成大于好</span></span><br><span class="line">            <span class="keyword">if</span> (mountainArr.get(mid) &gt; target) &#123;</span><br><span class="line">                l = mid + <span class="number">1</span>;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                r = mid;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 因为不确定区间收缩成 1个数以后，这个数是不是要找的数，因此单独做一次判断</span></span><br><span class="line">        <span class="keyword">if</span> (mountainArr.get(l) == target) &#123;</span><br><span class="line">            <span class="keyword">return</span> l;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[] arr = &#123;<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">3</span>, <span class="number">1</span>&#125;;</span><br><span class="line">        <span class="keyword">int</span> target = <span class="number">3</span>;</span><br><span class="line">        MountainArray mountainArray = <span class="keyword">new</span> MountainArrayImpl(arr);</span><br><span class="line"></span><br><span class="line">        Solution solution = <span class="keyword">new</span> Solution();</span><br><span class="line">        <span class="keyword">int</span> res = solution.findInMountainArray(target, mountainArray);</span><br><span class="line">        System.out.println(res);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度（OlogN）二分查找法的时间复杂度是对数级别的，这里使用了 3 次二分查找法，是常数倍数，因此可以忽略这个常数系数。</li>
<li>空间复杂度：O(1) 里使用的额外的辅助空间仅仅是 <code>mountaintop</code>、中位数索引 <code>mid</code> 等，是常数级别，因此空间复杂度为 O(1)。</li>
</ul>
<h1 id="3-分类2：在一个有范围的区间内找到一个整数"><a href="#3-分类2：在一个有范围的区间内找到一个整数" class="headerlink" title="3. 分类2：在一个有范围的区间内找到一个整数"></a>3. 分类2：在一个有范围的区间内找到一个整数</h1><h2 id="题目1-：-69：x-的平方根"><a href="#题目1-：-69：x-的平方根" class="headerlink" title="题目1 ： 69：x 的平方根"></a>题目1 ： <a href="https://leetcode-cn.com/problems/sqrtx/" target="_blank" rel="noopener">69：x 的平方根</a></h2><p><strong>题目描述</strong></p>
<ul>
<li>实现 <code>int sqrt(int x)</code> 函数。</li>
<li>计算并返回 x 的平方根，其中 x 是非负整数。</li>
<li>由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: 4</span><br><span class="line">输出: 2</span><br></pre></td></tr></table></figure>



<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">输入: 8</span><br><span class="line">输出: 2</span><br><span class="line">说明: 8 的平方根是 2.82842..., </span><br><span class="line">     由于返回类型是整数，小数部分将被舍去。</span><br></pre></td></tr></table></figure>



<p><strong>算法思路:二分查找</strong></p>
<ul>
<li><strong>二分查找法要找到左右边界</strong></li>
<li>一个数的平方根肯定不会超过它自己，还有比较细节的划分，那就是一个数的平方根不会超过它的一半。（比如8的平方根，一半是4，4的平方是16，大于8）</li>
<li><strong>因此我们要计算一下，这个右边界是多少</strong></li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200717/174153415.png" alt="mark"></p>
<p>意思就是：如果一个数的一般平方大于自己，那么这个数的取值范围。解以上不等式得 <code>a &gt;= 4 或者 a &lt; 0</code></p>
<ul>
<li>于是右边界的值就是4，因为边界值要大于0</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">mySqrt</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 对0的特殊处理</span></span><br><span class="line">        <span class="keyword">if</span> (x == <span class="number">0</span>)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 要把搜索的区间设置成长整型</span></span><br><span class="line">        <span class="comment">// 注意：针对特殊测试用例，例如 2147395599</span></span><br><span class="line">        <span class="keyword">long</span> left = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">long</span> right = x/<span class="number">2</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">long</span> mid = (left + right + <span class="number">1</span>) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">long</span> square = mid * mid;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 排除大于不是解</span></span><br><span class="line">            <span class="keyword">if</span> (square &gt; x)&#123;</span><br><span class="line">                right = mid - <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                left = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 注意返回的是整型</span></span><br><span class="line">        <span class="keyword">return</span> (<span class="keyword">int</span>) left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析</strong></p>
<ul>
<li><strong>时间复杂度</strong>：O(logN),二分查找的时间复杂度是对数级别的</li>
<li><strong>空间复杂度</strong>：O(1) 使用了常数个数的辅助空间用于存储</li>
</ul>
<h2 id="题目2：-287-寻找重复数"><a href="#题目2：-287-寻找重复数" class="headerlink" title="题目2：  287. 寻找重复数"></a>题目2：  <a href="https://leetcode-cn.com/problems/find-the-duplicate-number/" target="_blank" rel="noopener">287. 寻找重复数</a></h2><p><strong>题目描述</strong></p>
<ul>
<li>给定一个包含 <code>n + 1</code>个整数的数组 <code>nums</code>，其数字都在 <code>1 到 n 之间</code>（包括 1 和 n），可知至少存在一个重复的整数。假设<strong>只有一个重复的整数</strong>，找出这个重复的数。</li>
</ul>
<p><strong>示例 1:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: [1,3,4,2,2]</span><br><span class="line">输出: 2</span><br></pre></td></tr></table></figure>

<p><strong>示例 2:</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: [3,1,3,4,2]</span><br><span class="line">输出: 3</span><br></pre></td></tr></table></figure>



<p>说明：</p>
<ul>
<li><strong>不能更改原数组（假设数组是只读的）。</strong></li>
<li>只能使用额外的 O(1) 的空间。</li>
<li>时间复杂度小于 O(n^2) 。</li>
<li>数组中只有一个重复的数字，但它可能不止重复出现一次。</li>
</ul>
<p><strong>Solution：二分法</strong></p>
<ul>
<li><p><strong>如果测试数据不在这个范围里，二分法失效</strong>。</p>
</li>
<li><p><strong>二分法的常见作用：可以用来确定一个有范围的整数</strong></p>
</li>
</ul>
<ul>
<li>预备知识：</li>
</ul>
<p><strong>抽屉原理</strong>：假设要把10个苹果放进9个柜子，那么一定有一个柜子放了不止一个。</p>
<p>容易想到的方法有：</p>
<ul>
<li>使用哈希表判重，这违反了限制 2；</li>
<li>将原始数组排序，排序以后，重复的数相邻，即找到了重复数，这违反了限制 1；</li>
<li>使用类似「力扣」第 41 题：缺失的第一个正数 （原地哈希）的思路，当两个数发现要放在同一个地方的时候，就发现了这个重的元素，这违反了限制 1；</li>
<li>既然要定位数，这个数恰好是一个整数，可以在「整数的有效范围内」做二分查找，但是比较烦的一点是得反复看整个数组好几次，本题解就介绍通过二分法定位一个有范围的整数；</li>
<li>还可以使用「快慢指针」来完成，不过这种做法太有技巧性了，不是通用的做法，可以查看官方题解。</li>
</ul>
<p><strong>思路：</strong></p>
<ul>
<li><p>二分法的思路是先猜一个数（有效范围 <code>[left, right]</code>里的中间数 <code>mid</code>）</p>
</li>
<li><p>然后统计原始数组中<strong>小于等于</strong>这个中间数的元素的个数 count , 如果count <strong>严格大于</strong> mid ，注意我加了着重号的部分「小于等于」、「严格大于」）。</p>
</li>
<li><p>根据抽屉原理，重复的元素就在区间 <code>[left, mid]</code> 里；</p>
</li>
</ul>
<p><strong>举个例子：</strong></p>
<ul>
<li>以<code>[2,4,5,2,3,1,6,7]</code> 为例，一共 8 个数，<code>n + 1 = 8</code>  那么 n = 7 并且根据题目的意思，每个数都在[1,7]之间</li>
<li>例如：区间[1,7]的中位数是4<ul>
<li>之后遍历整个数组，统计小于等于4的整数的个数，如果不存在重复元素，最后就是4个。</li>
<li>等于4的时候区间[1,4]内也可能有重复的元素，比如 [1,2,2,4] 。</li>
<li>但是,如果整个数组里小于等于4的正数的个数严格大于4 的时候，根据抽屉原理，一定说明重复的数字在[1,4]之间。</li>
</ul>
</li>
</ul>
<p><strong>Solution : 算法</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findDuplicate</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> len = nums.length;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> right = len - <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="comment">//在 Java 里可以这么用，</span></span><br><span class="line">            <span class="comment">// 当 left + right 溢出的时候，无符号右移保证结果依然正确</span></span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 每次更新 count 会被重置为0</span></span><br><span class="line">            <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 统计原始数组中小于等于这个中间数元素的个数count</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">                <span class="keyword">if</span> (num &lt;= mid)&#123;</span><br><span class="line">                    count += <span class="number">1</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 根据抽屉原理，count如果严格大于mid个</span></span><br><span class="line">            <span class="comment">// 此时重复元素一定在[1,mid]之间</span></span><br><span class="line">            <span class="keyword">if</span> (count &gt; mid)&#123;</span><br><span class="line">                <span class="comment">// 重复元素位于[left,mid]之间</span></span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">// 重复元素位于[mid + 1, right] 之间</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// left = right 的时候推出循环，结果就是重复的数字</span></span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<ul>
<li><strong>时间复杂度：O(nlogn)</strong> - 二分法的时间复杂度是O(logn) ,并且在二分法内部执行了一次 for 循环 ，时间复杂度是O(n), 所以总的复杂度是O(nlogn)。</li>
<li><strong>空间复杂度O(1)</strong> : 使用了一个count变量</li>
</ul>
<h2 id="题目3-：-374-猜数字大小"><a href="#题目3-：-374-猜数字大小" class="headerlink" title="题目3 ： 374. 猜数字大小"></a>题目3 ： <a href="https://leetcode-cn.com/problems/guess-number-higher-or-lower/" target="_blank" rel="noopener">374. 猜数字大小</a></h2><p><strong>题目描述</strong></p>
<p>我们正在玩一个猜数字游戏。 游戏规则如下：<br>我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。<br>每次你猜错了，我会告诉你这个数字是大了还是小了。<br>你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">-1 : 我的数字比较小</span><br><span class="line"> 1 : 我的数字比较大</span><br><span class="line"> 0 : 恭喜！你猜对了！</span><br></pre></td></tr></table></figure>



<p><strong>示例 :</strong></p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: n &#x3D; 10, pick &#x3D; 6</span><br><span class="line">输出: 6</span><br></pre></td></tr></table></figure>





<p><strong>算法思想：</strong></p>
<ol>
<li><strong>首先得先把guessnum接口先写出来</strong></li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GuessGame</span></span>&#123;</span><br><span class="line">    <span class="comment">// 比如我猜的数字是6</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> NUM = <span class="number">6</span>;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">guess</span><span class="params">(<span class="keyword">int</span> num)</span></span>&#123;</span><br><span class="line">        <span class="comment">// 你和我猜的一样</span></span><br><span class="line">        <span class="keyword">if</span> (num == NUM)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span> (num &lt; NUM)&#123;</span><br><span class="line">            <span class="comment">// 你猜的比我猜的小</span></span><br><span class="line">            <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 你猜的比我猜的大</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<ol start="2">
<li><strong>接下来的思路就很显然了</strong><ul>
<li>排除猜错的区间 <code>guessNum = -1</code> 的情况，那么下一轮搜索区间是<code>[left,mid - 1]</code></li>
</ul>
</li>
</ol>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> <span class="keyword">extends</span> <span class="title">GuessGame</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">guessNumber</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> right = n;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right + <span class="number">1</span>) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">int</span> guessNum = guess(mid);</span><br><span class="line">            <span class="keyword">if</span> (guessNum == -<span class="number">1</span>)&#123;</span><br><span class="line">                <span class="comment">// 中位数比猜的数大</span></span><br><span class="line">                right = mid - <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                left = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 最后一定会猜对</span></span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li><strong>时间复杂度：O(logn)</strong></li>
<li><strong>空间复杂度： O(1)</strong> </li>
</ul>
<h2 id="题目4-：-1300-转变数组后最接近目标值的数组和"><a href="#题目4-：-1300-转变数组后最接近目标值的数组和" class="headerlink" title="题目4 ： 1300. 转变数组后最接近目标值的数组和"></a>题目4 ： <a href="https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/" target="_blank" rel="noopener">1300. 转变数组后最接近目标值的数组和</a></h2><p><strong>题目描述</strong></p>
<p>给你一个整数数组 <code>arr</code> 和一个目标值 <code>target</code> ，请你返回一个<code>整数 value</code> ，<strong>使得将数组中所有大于 value 的值变成 value 后，数组的和最接近  target （最接近表示两者之差的绝对值最小）。</strong></p>
<p>如果有多种使得和最接近 <code>target</code> 的方案，请你返回这些整数中的最小值。</p>
<p>请注意，答案不一定是 <code>arr</code> 中的数字。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">示例 1：</span><br><span class="line"></span><br><span class="line">输入：arr &#x3D; [4,9,3], target &#x3D; 10</span><br><span class="line">输出：3</span><br><span class="line">解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">示例 2：</span><br><span class="line"></span><br><span class="line">输入：arr &#x3D; [2,3,5], target &#x3D; 10</span><br><span class="line">输出：5</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">示例 3：</span><br><span class="line"></span><br><span class="line">输入：arr &#x3D; [60864,25176,27249,21296,20204], target &#x3D; 56803</span><br><span class="line">输出：11361</span><br></pre></td></tr></table></figure>

<p><strong>提示：</strong></p>
<ul>
<li><code>1 &lt;= arr.length &lt;= 10^4</code></li>
<li><code>1 &lt;= arr[i], target &lt;= 10^5</code></li>
</ul>
<p><strong>方法：二分查找</strong></p>
<p><strong>思路：</strong></p>
<ul>
<li>使用二分法确定一个正数<code>threshold</code>,使得这个<code>threshold</code>下，转变后的数组的和最接近目标值<code>target</code><ul>
<li>转变的规则是严格大于<code>threshold</code>元素变成<code>threshold</code>，那么也就意味着<code>threshold</code>越大，数组的和越大（注意这里是单调的，也有可能<code>threshold</code>扩大之后，和可能不变，也就是<strong>大于等于的关系</strong>）</li>
</ul>
</li>
</ul>
<ul>
<li>正是因为题目说 <code>value</code> 是整数，并且「答案不一定是 <code>arr</code> 中的数字」，因此依然可以使用二分查找法确定这个整数值。</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200719/144801332.png" alt="mark"></p>
<ul>
<li><strong>做题的时候，发现最难写的其实是判断的条件，因为「怎么衡量接近」，度量这个「最接近」的量不好选。因此需要考虑别的方案；</strong></li>
</ul>
<ul>
<li><strong>这里问题就是：选定了一个value求和之后，</strong><ul>
<li>如果恰恰好等于 <code>target</code> ，那就万事大吉</li>
<li>不过更可能出现的情况是， value 取小了，接近程度变大</li>
<li>而value 取大了之后，接近程度变小了</li>
</ul>
</li>
</ul>
<p><img src="http://zhuuu-bucket.oss-cn-beijing.aliyuncs.com/img/20200719/145036767.png" alt="mark"></p>
<ul>
<li><strong>解决方案</strong><ul>
<li><strong>先用二分法确定value的可能的值</strong></li>
<li><strong>然后把value的上下边界都拿出来进行一次比较</strong></li>
</ul>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">findBestValue</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span>  left  = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span>  right = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 取最大的数置为right</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num : arr) &#123;</span><br><span class="line">            right = Math.max(num,right);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">int</span> sum = calculateSum(arr,mid);</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 计算第一个使得转变后数组的和大于等于target的阈值</span></span><br><span class="line">            <span class="keyword">if</span> (sum &lt; target)&#123;</span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 判断到底返回的是哪个阈值</span></span><br><span class="line">        <span class="comment">// 比较阈值线分别在left - 1 和 left的时候与target的接近程度</span></span><br><span class="line">        <span class="keyword">int</span> sum1 = calculateSum(arr,left - <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">int</span> sum2 = calculateSum(arr,left);</span><br><span class="line">        <span class="comment">// 判断接近程度</span></span><br><span class="line">        <span class="keyword">if</span> (target - sum1 &lt;= sum2 - target)&#123;</span><br><span class="line">            <span class="keyword">return</span> left -  <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/// 计算数组中threshold以下数字的和</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">calculateSum</span><span class="params">(<span class="keyword">int</span>[] arr, <span class="keyword">int</span> threshold)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num : arr) &#123;</span><br><span class="line">            sum += Math.min(num,threshold);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sum;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Test</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        Solution solution = <span class="keyword">new</span> Solution();</span><br><span class="line">        System.out.println(solution.findBestValue(<span class="keyword">new</span> <span class="keyword">int</span>[]&#123;<span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>&#125;, <span class="number">10</span>));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>复杂度分析</strong></p>
<ul>
<li><p>时间复杂度：O(NlogN)，这里 N 是输入数组的长度，二分的时间复杂度是 O(logN)，每一次 calculateSum 的时间复杂度是 O(N)；</p>
</li>
<li><p>空间复杂度：O(1)。</p>
</li>
</ul>
<h2 id="题目5-：-1283-使结果不超过阈值的最小除数"><a href="#题目5-：-1283-使结果不超过阈值的最小除数" class="headerlink" title="题目5 ： 1283. 使结果不超过阈值的最小除数"></a>题目5 ： <a href="https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold/" target="_blank" rel="noopener">1283. 使结果不超过阈值的最小除数</a></h2><p><strong>题目描述</strong></p>
<ul>
<li>给你一个整数数组 <code>nums</code> 和一个正整数 <code>threshold</code>，选择一个正整数作为除数，然后将数组里的每个数都除以它，并对除法结果求和。</li>
<li>请你找出能够使得上述结果小于等于阈值 <code>threshold</code> 的除数<strong>最小</strong>的那个</li>
<li>每个数除以除数之后都会向上取整，比方说 7/3 = 3 ， 10/2 = 5 。</li>
</ul>
<figure class="highlight html"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">示例 1：</span><br><span class="line"></span><br><span class="line">输入：nums = [1,2,5,9], threshold = 6</span><br><span class="line">输出：5</span><br><span class="line">解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。</span><br><span class="line">如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。</span><br><span class="line"></span><br><span class="line">    </span><br><span class="line">示例 2：</span><br><span class="line"></span><br><span class="line">输入：nums = [2,3,5,7,11], threshold = 11</span><br><span class="line">输出：3</span><br><span class="line"></span><br><span class="line">示例 3：</span><br><span class="line"></span><br><span class="line">输入：nums = [19], threshold = 5</span><br><span class="line">输出：4</span><br></pre></td></tr></table></figure>



<p><strong>方法思路</strong></p>
<ol>
<li>找出小于等于阈值 <code>threshold</code> 中<strong>最小</strong>的那个，明显可以使用二分查找</li>
<li>于是可以思考除数最大可以是多少，最小是多少<ul>
<li><strong>最大是数组中最大的那个数</strong>，因为除数如果再大，整除以后每个数都得 1（上取整的缘故）；</li>
<li><strong>最小可以是 1。</strong></li>
</ul>
</li>
</ol>
<ol start="3">
<li>写 if  分支的时候，根据题目的意思选<ul>
<li>选择一个正整数作为除数，然后将数组重的每个数都除以它，并对除法结果求和</li>
</ul>
</li>
<li><strong>这时候开始思考二分查找的关键  ： 排除什么时候不是解</strong><ul>
<li>因此 ： 和<strong>严格</strong>大于 阈值<code>threshold</code> 的整数，一定不是解。根据减而治之的思想， 定位这个除数。</li>
</ul>
</li>
</ol>
<p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">smallestDivisor</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> threshold)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 先找数组中的最大值，用最大值作为除数，除完以后和最小</span></span><br><span class="line">        <span class="keyword">int</span> maxVal = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">            maxVal = Math.max(maxVal, num);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 注意：最小值是 1，因为 threshold 可以很大</span></span><br><span class="line">        <span class="keyword">int</span> left = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">int</span> right = maxVal;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right) &#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (calculateSum(nums, mid) &gt; threshold) &#123;</span><br><span class="line">                <span class="comment">// sum 大于阈值一定不是解，说明除数选得太小了</span></span><br><span class="line">                <span class="comment">// 下一轮搜索区间是 [mid + 1, right]</span></span><br><span class="line">                <span class="comment">// （把下一轮搜索区间写出来，边界选择就不会错）</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">                <span class="comment">// 边界是 left = mid + 1 ，中间数不用上取整</span></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> nums</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> divisor</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 数组中各个元素与 divisor 相除的结果（向上取整）之和</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">calculateSum</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> divisor)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) &#123;</span><br><span class="line">            sum += num / divisor;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 注意：不能整除的时候，需要向上取整</span></span><br><span class="line">            <span class="keyword">if</span> (num % divisor != <span class="number">0</span>) &#123;</span><br><span class="line">                sum++;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sum;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度：ONlogmaxnums 这里 <em>N</em> 是数组的长度，每一次二分都执行了边界判断函数，都得遍历一遍数组；</li>
<li>空间复杂度：<em>O(1)</em>。</li>
</ul>
<h2 id="题目6-：-875-爱吃香蕉的珂珂"><a href="#题目6-：-875-爱吃香蕉的珂珂" class="headerlink" title="题目6 ： 875. 爱吃香蕉的珂珂"></a>题目6 ： <a href="https://leetcode-cn.com/problems/koko-eating-bananas/" target="_blank" rel="noopener">875. 爱吃香蕉的珂珂</a></h2><p><strong>题目描述</strong></p>
<p>珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。</p>
<p>珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  </p>
<p>珂珂<strong>喜欢慢慢吃</strong>，但仍然想在警卫回来前吃掉所有的香蕉。</p>
<p>返回她可以在 <strong>H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。</strong></p>
<p><strong>思路</strong></p>
<ul>
<li>最小速度是1，最大速度是数组重的最大值。</li>
</ul>
<p><strong>代码实现</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">minEatingSpeed</span><span class="params">(<span class="keyword">int</span>[] piles, <span class="keyword">int</span> H)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 得到速度的最大值</span></span><br><span class="line">        <span class="keyword">int</span> maxVal = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> pile : piles) &#123;</span><br><span class="line">            maxVal = Math.max(maxVal,pile);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 速度的最小值</span></span><br><span class="line">        <span class="keyword">int</span> left  = <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 速度的最大值</span></span><br><span class="line">        <span class="keyword">int</span> right = maxVal;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (left &lt; right)&#123;</span><br><span class="line">            <span class="keyword">int</span> mid = (left + right) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// 排除：吃的太慢的情况</span></span><br><span class="line">            <span class="keyword">if</span> (calculateSum(piles,mid) &gt; H)&#123;</span><br><span class="line">                <span class="comment">// 下一轮搜索区间[mid + 1,right]</span></span><br><span class="line">                left = mid + <span class="number">1</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                right = mid;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> left;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">calculateSum</span><span class="params">(<span class="keyword">int</span>[] piles,<span class="keyword">int</span> speed)</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span> sum = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> pile : piles) &#123;</span><br><span class="line">            <span class="comment">// 除不尽向上取整</span></span><br><span class="line">            sum += pile / speed;</span><br><span class="line">            <span class="keyword">if</span>(pile % speed != <span class="number">0</span>)&#123;</span><br><span class="line">                sum += <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> sum;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>复杂度分析</strong></p>
<ul>
<li>时间复杂度：ONlogmaxnums 这里 <em>N</em> 是数组的长度，每一次二分都执行了边界判断函数，都得遍历一遍数组；</li>
<li>空间复杂度：<em>O(1)</em>。</li>
</ul>

      
      <!-- reward -->
      
      <div id="reward-btn">
        打赏
      </div>
      
    </div>
      <!-- copyright -->
      
        <div class="declare">
          <ul class="post-copyright">
            <li>
              <i class="ri-copyright-line"></i>
              <strong>版权声明： </strong s>
              本博客所有文章除特别声明外，均采用 <a href="https://www.apache.org/licenses/LICENSE-2.0.html" rel="external nofollow"
                target="_blank">Apache License 2.0</a> 许可协议。转载请注明出处！
            </li>
          </ul>
        </div>
        
    <footer class="article-footer">
      
          
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=http://zhuuu.work/2020/07/02/LeetcodeExplore/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE-%E5%90%88%E9%9B%86/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Leetcode/" rel="tag">Leetcode</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/" rel="tag">二分查找</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/" rel="tag">算法总结</a></li></ul>


    </footer>

  </div>

  
  
  <nav class="article-nav">
    
      <a href="/2020/07/05/JUC/JUC-15-%E7%BA%BF%E7%A8%8B%E5%92%8C%E8%BF%9B%E7%A8%8B/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            JUC-15-线程和进程总结
          
        </div>
      </a>
    
    
      <a href="/2020/07/01/Leetcode/LCP-022-%E9%BB%91%E7%99%BD%E6%A0%BC%E6%96%B9%E7%94%BB/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">LCP-22-黑白方格画阶</div>
      </a>
    
  </nav>


  

  
  
<!-- valine评论 -->
<div id="vcomments-box">
    <div id="vcomments">
    </div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src='https://cdn.jsdelivr.net/npm/valine@1.3.10/dist/Valine.min.js'></script>
<script>
    new Valine({
        el: '#vcomments',
        notify: false,
        verify: '',
        app_id: '',
        app_key: '',
        path: window.location.pathname,
        avatar: 'mp',
        placeholder: '给我的文章加点评论吧~',
        recordIP: true
    });
    const infoEle = document.querySelector('#vcomments .info');
    if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
        infoEle.childNodes.forEach(function (item) {
            item.parentNode.removeChild(item);
        });
    }
</script>
<style>
    #vcomments-box {
        padding: 5px 30px;
    }

    @media screen and (max-width: 800px) {
        #vcomments-box {
            padding: 5px 0px;
        }
    }

    #vcomments-box #vcomments {
        background-color: #fff;
    }

    .v .vlist .vcard .vh {
        padding-right: 20px;
    }

    .v .vlist .vcard {
        padding-left: 10px;
    }
</style>

  

  
  
<div class="gitalk" id="gitalk-container"></div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.css">


<script src="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.js"></script>


<script src="https://cdn.jsdelivr.net/npm/blueimp-md5@2.10.0/js/md5.min.js"></script>

<script type="text/javascript">
  var gitalk = new Gitalk({
    clientID: 'db188ed8c86dc4b0dbf3',
    clientSecret: 'a58f92160e5a9efd726b7d533000a0737f3e3f3e',
    repo: 'Blog-comments',
    owner: 'Zhuuuuuuuu',
    admin: ['Zhuuuuuuuu'],
    // id: location.pathname,      // Ensure uniqueness and length less than 50
    id: md5(location.pathname),
    distractionFreeMode: false,  // Facebook-like distraction free mode
    pagerDirection: 'last'
  })

  gitalk.render('gitalk-container')
</script>

  

</article>
</section>
      <footer class="footer">
  <div class="outer">
    <ul class="list-inline">
      <li>
        &copy;
        2019-2021
        Zhuuu
      </li>
      <li>
        
      </li>
    </ul>
    <ul class="list-inline">
      <li>
        
        
        <span>
  <i>PV:<span id="busuanzi_value_page_pv"></span></i>
  <i>UV:<span id="busuanzi_value_site_uv"></span></i>
</span>
        
      </li>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s9.cnzz.com/z_stat.php?id=1278069914&amp;web_id=1278069914'></script>
        
      </li>
    </ul>
  </div>
</footer>
    <div class="to_top">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>
      </div>
    </main>
      <aside class="sidebar">
        <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="朱酱酱的学习博客"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">主页</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">标签</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JVM/">JVM</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/JDK%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/">JDK源码</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%A4%9A%E7%BA%BF%E7%A8%8B/">多线程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Mysql/">Mysql</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Redis/">Redis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E8%AE%BE%E8%AE%A1%E8%80%85%E6%A8%A1%E5%BC%8F/">设计模式</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/MyBatis/">MyBatis</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringMVC/">SpringMVC</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Spring/">Spring</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/SpringBoot/">SpringBoot</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/">Linux</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/Leetcode/">Leetcode</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E5%89%8D%E7%AB%AF/">前端</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B/">网络编程</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/photoshop/">photoshop</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="http://smartzhuuu.lofter.com/" target="_blank" rel="noopener">摄影</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/about">关于我</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="Search">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
      </aside>
      <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯咖啡吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
      
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/jquery.justifiedGallery.min.js"></script>


<script src="/js/lazyload.min.js"></script>


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<script src="/js/share.js"></script>



<script src="/fancybox/jquery.fancybox.min.js"></script>




<script>
  try {
    var typed = new Typed("#subtitle", {
    strings: ['昨夜西风凋碧树。独上高楼，望尽天涯路','衣带渐宽终不悔，为伊消得人憔悴。','众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。'],
    startDelay: 0,
    typeSpeed: 200,
    loop: true,
    backSpeed: 100,
    showCursor: true
    });
  } catch (err) {
  }
  
</script>




<script src="/js/tocbot.min.js"></script>

<script>
  // Tocbot_v4.7.0  http://tscanlin.github.io/tocbot/
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer:'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto',
    onClick: (e) => {
      $('.toc-link').removeClass('is-active-link');
      $(`a[href=${e.target.hash}]`).addClass('is-active-link');
      $(e.target.hash).scrollIntoView();
      return false;
    }
  });
</script>


<script>
  var ayerConfig = {
    mathjax: true
  }
</script>


<script src="/js/ayer.js"></script>


<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">


<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>



<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>


<script type="text/javascript" src="https://js.users.51.la/20544303.js"></script>
  </div>
</body>

</html>